package com.mango.algorithm.sort;

import com.google.common.base.Stopwatch;

import java.util.Arrays;
import java.util.concurrent.TimeUnit;

/**
 * 快速排序
 * 空间复杂度：O(nLogN)
 * 时间复杂度：O(nLogN)
 *
 * 思路：
 * 1. 先选择一个基准点P，以基准点P做分区操作（将比P小的数放到P的左边，比P大的数放到右边）
 * 2. 然后递归在左边0-P的部分排序，sort(0,P)
 * 3. 再递归排右边部分sort(p+1,len)
 * 4. 如果left>=right,则退出
 *
 * 例子：
 * old:[13, 7, 4, 6, 9, 24]
 * partition: old=[13, 7, 4, 6, 9, 24]
 * partition: left=0,right=5,value=4,j=0,swapCount=2 [4, 7, 13, 6, 9, 24]
 * partition: old=[7, 13, 6, 9, 24]
 * partition: left=1,right=5,value=6,j=1,swapCount=2 [6, 13, 7, 9, 24]
 * partition: old=[13, 7, 9, 24]
 * partition: left=2,right=5,value=7,j=2,swapCount=2 [7, 13, 9, 24]
 * partition: old=[4, 6]
 * partition: left=0,right=1,value=4,j=0,swapCount=2 [4, 6]
 * partition: old=[13, 9, 24]
 * partition: left=3,right=5,value=9,j=3,swapCount=2 [9, 13, 24]
 * partition: old=[4, 6, 7]
 * partition: left=0,right=2,value=6,j=1,swapCount=3 [4, 6, 7]
 * partition: old=[13, 24]
 * partition: left=4,right=5,value=13,j=4,swapCount=2 [13, 24]
 * partition: old=[4, 6, 7, 9]
 * partition: left=0,right=3,value=6,j=1,swapCount=3 [4, 6, 7, 9]
 * partition: old=[7, 9]
 * partition: left=2,right=3,value=7,j=2,swapCount=2 [7, 9]
 * partition: old=[4, 6]
 * partition: left=0,right=1,value=4,j=0,swapCount=2 [4, 6]
 * result:[4, 6, 7, 9, 13, 24]耗时:5ms
 *
 *
 */
public class QuickSort {
    public static void main(String[] args) {
        Stopwatch sw = Stopwatch.createStarted();
        int[] nums = {13,7,4,6,9,24};
        System.out.println("old:"+ Arrays.toString(nums));
        System.out.println("result:"+Arrays.toString(sort(nums))+"耗时:"+sw.elapsed(TimeUnit.MILLISECONDS)+"ms");
    }

    public static int[] sort(int[] nums){
        quickSort(nums,0,nums.length-1);
        return nums;
    }
    // 快速排序
    public static void quickSort(int[] nums,int left,int right){
        if(left >= right){
            return ;
        }
        // 基准坐标，分区
        int p = partition(nums,left,right);
        // 递归排左边的
        quickSort(nums,0,p-1);
        // 递归排右边的
        quickSort(nums,p+1,right);
    }

    // 对arr[l...r]部分进行partition操作
    // 返回index, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
    private static int partition(int[] nums, int left, int right) {
        // 基准值
        int[] newNums = Arrays.copyOfRange(nums,left,right+1);
        int p = (left + right) / 2;
        // 将基准值和left交换
        int swapCount = 2;
        swap(nums, left, p);
        int value = nums[left];

        int j = left;
        for (int i = left + 1; i <= right; i++){
            if (nums[i] < value) {
                j++;
                swap(nums, j, i);
                swapCount ++;
            }
        }
        swap(nums, left, j);

        System.out.println("partition: old="+Arrays.toString(newNums));
        int[] sortNums = Arrays.copyOfRange(nums,left,right+1);
        System.out.println("partition: left="+left+",right="+right+",value=" + value + ",j=" + j + ",swapCount=" + swapCount + " " + Arrays.toString(sortNums));

        return j;
    }

    // 交换数组下标
    public static void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
